/*
* 最小生成树算法解析
* Prim 朴素 O(n^2) 邻接矩阵 枚举点 不可堆优化 

* Krusal O(mlogm) 存边 维护连通性使用并查集 已是最小生成树，加任意一条边就存在环，此时需要判决

* 最小生成树理论基础:
* 1．任意一棵最小生成树一定可以包含无向图中权值最小的边。
* 2．给定一张无向图G=(V,E),n=|V|, m=|E|。从E中选出k<n-1条边构成G的加一个生成森林。
     然后在剩余的m-k条边中选n-1-k条边添加到生成森林中，使其成为G的生成树，并且选出的边的权值之和最小。
     则该生成树一定可以包含m-k条边中连接生成森林的两个不连通节点的权值最小的边。

* Krusal算法:
* 1.先将所有边按边权从小到大排序
* 2.从小到大扫描所有边, 依次将没有合并的点集合并
    假设当前已经循环完第i条边，已经求出了由前i条边所构成的

* 一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，代码中的操作次数控制在 10 ^ 7 ∼ 10 ^ 8 为最佳。
    n <= 100 -> O(n ^ 3) -> 状态压缩dp floyd 高斯消元
    n <= 1000 -> O(n ^ 2) O(n ^ 2 * log(n)) -> dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
    n ≤ 100000 -> O(nlogn) -> 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa
*/
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
// #define ONLINE_GUDGE
using namespace std;
const int N = 6010, INF = 0x3f3f3f3f;

int n;
// Krusal
struct Edge{    //用结构体存储每条边
    int from, to;
    int w;
    bool operator<(const Edge &e)const{
        return w < e.w;
    }
}edges[N];

int fa[N], sz[N]; // 并查集 每个连通块中节点数量

int find(int x){    //并查集找根节点
    return fa[x] = (fa[x] == x ? x : find(fa[x]));
}

int main()
{
    #ifdef ONLINE_JUDGE

    #else
        freopen("./in.txt", "r", stdin);
    #endif

    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    while(T--)
    {

        cin >> n;

        for(int i = 0; i < n-1; i++){
                int a, b, w; cin >> a >> b >> w;
                edges[i] = Edge{a, b, w};  //加入当前的边
            }
        sort(edges, edges+n-1);  //对边进行排序

        for(int i = 1; i <= n; i++)
            fa[i] = i, sz[i] = 1;    //并查集初始化

        int ans = 0;

        for(int i = 0; i < n - 1; i++){

            int f = find(edges[i].from), t = find(edges[i].to), w = edges[i].w;

            if(f != t){   //当前两点不连通
                ans += (sz[f] * sz[t] - 1) * (w + 1);    //保证最小生成树不变，即加入边永远不会被选
                sz[t] += sz[f];
                fa[f] = t;    //让两点变连通
            }
        }

        cout << ans << endl;
    }
    return 0;
} 